package com.ma.DataStruct;

import java.util.HashMap;
import java.util.Stack;

public class Solution895 {
    public static void main(String[] args) {
        FreqStack stk = new FreqStack();

        // 向最大频率栈中添加元素
        stk.push(2);
        stk.push(7);
        stk.push(2);
        stk.push(7);
        stk.push(2);
        stk.push(4);

        // 栈中元素：[2,7,2,7,2,4]

        System.out.println(stk.pop()); // 返回 2
        // 因为 2 出现了三次

        // 栈中元素：[2,7,2,7,4]

        System.out.println(stk.pop()); // 返回 7
        // 2 和 7 都出现了两次，但 7 是最近添加的

        // 栈中元素：[2,7,2,4]

        System.out.println(stk.pop()); // 返回 2

        // 栈中元素：[2,7,4]

        System.out.println(stk.pop()); // 返回 4

        // 栈中元素：[2,7]
    }
}

/*
 * 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
 * 实现 FreqStack类:
 *
 *      FreqStack()构造一个空的堆栈。
 *      void push(int val)将一个整数val压入栈顶。
 *      int pop()删除并返回堆栈中出现频率最高的元素。
 *          如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
 * 参考LFU,设计该数据结构需要频率
 *      每次pop()时要知道频率最高的元素是谁,如果有多个，还需要知道最近被push的元素
 *          - 添加字段 maxFreq 记录当前栈中最高的频率是多少
 *          - 记录当前频率对应的元素有哪些 FreqToVal
 *          - 调用pop,该val的频率+1，需要ValToFreq
 *

 */
class FreqStack {

    private int maxFreq;
    private HashMap<Integer, Integer> valToFreq;
    private HashMap<Integer, Stack<Integer>> freqToVals;

    public FreqStack() {
        this.maxFreq = 0;
        this.valToFreq = new HashMap<>();
        this.freqToVals = new HashMap<>();

    }

    public void push(int val) {
        // 修改 VF 表：val 对应的 freq 加一
        int freq = valToFreq.getOrDefault(val, 0) + 1;
        valToFreq.put(val, freq);
        // 修改 VF 表：val 对应的 freq 加一
        freqToVals.putIfAbsent(freq, new Stack<>());
        freqToVals.get(freq).push(val);
        // 更新 maxFreq
        maxFreq = Math.max(maxFreq, freq);

    }

    public int pop() {
        // 修改 FV 表：pop 出一个 maxFreq 对应的元素 v
        Stack<Integer> vals = freqToVals.get(maxFreq);
        int v = vals.pop();
        // 修改 VF 表：v 对应的 freq 减一
        int freq = valToFreq.get(v) - 1;
        valToFreq.put(v, freq);
        // 修改 VF 表：v 对应的 freq 减一
        if (vals.isEmpty()) {
            // 修改 VF 表：v 对应的 freq 减一
            maxFreq--;
        }
        return v;
    }
}
